package org.yanse.structures.array;

/**
 * 稀疏数组（二维数组）
 * 作用 压缩数据
 * 原理
 *     1.不存储默认值
 *     2. 固定3列
 *     3.第一行存储原数组的行、列、有效元素数量
 *     4.每行依次存储有效元素行、列、值
 * 示例
 *     二维数组
 *     1 0 0 1
 *     2 0 0 1
 *     0 1 2 3
 *     稀疏数组
 *     3 4 7
 *     0 0 1
 *     0 3 1
 *     1 0 2
 *     1 3 1
 *     2 1 1
 *     2 2 2
 *     2 3 3
 */
public class SparseArray {
    public static int[][] normalToSparse(int[][] normal, int defaultValue) {
        if (normal == null || normal.length == 0) {
            return normal;
        }

        // 有效元素数量
        int count = 0;
        for (int[] ints : normal) {
            for (int value : ints) {
                if (value != defaultValue) {
                    count++;
                }
            }
        }

        // 有效元素 + 行列
        int[][] sparse = new int[count + 1][3];
        sparse[0][0] = normal.length;
        sparse[0][1] = normal[0].length;
        sparse[0][2] = count;

        // 稀疏数组当前行
        int index = 1;

        for (int i = 0; i < normal.length; i++) {
            for (int j = 0; j < normal[i].length; j++) {
                if (normal[i][j] != defaultValue) {
                    sparse[index][0] = i;
                    sparse[index][1] = j;
                    sparse[index][2] = normal[i][j];
                    index++;
                }
            }
        }
        return sparse;
    }

    public static int[][] sparseToNormal(int[][] sparse, int defaultValue) {
        if (sparse == null || sparse.length == 0) {
            return sparse;
        }
        int row = sparse[0][0];
        int col = sparse[0][1];
        int[][] normal = new int[row][col];
        if (defaultValue != 0) {
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    normal[i][j] = defaultValue;
                }
            }
        }

        for (int i = 1; i < sparse.length; i++) {
            normal[sparse[i][0]][sparse[i][1]] = sparse[i][2];
        }

        return normal;
    }
}
